"""
Finite state acceptors, transducers, and regular expressions over feature
bundles and phonological forms (i.e., C{pyphon.Symbol}s and C{pyphon.Form}s).
"""

import pyphon
import operator, codecs, copy, sys
from pprint import pprint
from copy import deepcopy

#=============================================================================

nodeNum = 0
def nextNode(data=None):
    """
    Returns a new Node, with an id guaranteed to be unique from all previous
    and subsequent requests.
    """
    global nodeNum
    #node = 'n%d' % nodeNum
    nodeNum += 1
    return Node(nodeNum, data)

#=============================================================================

class Node(object):
    def __init__(self, id, data=None):
        if isinstance(id, Node):
            # copy... deep copy the data?
            self.id = id.id
            if data:
                self.data = data
            else:
                self.data = id.data
        else:
            self.id = id
            self.data = data

    def dot(self):
        if self.data:
            return "%s\\n%s" % (self, self.data)
        else:
            return str(self)

    def __str__(self):
        return str(self.id)

    def __repr__(self):
        if self.data:
            return 'Node(%r, %r)' % (self.id, self.data)
        return 'Node(%r)' % (self.id,)

    def __eq__(self, other):
        return self.id == other.id

    def __ne__(self, other):
        return self.id != other.id

    def __hash__(self):
        return hash(self.id)

#=============================================================================

AnySymbol = pyphon.Symbol()
AnySymbol.uStr = "@"

class Label(object):
    def __init__(self, *args, **kwargs):
        self.input = None
        self.output = None
        self.weight = None

        if len(args) == 1:
            if isinstance(args[0], Label):
                #copy
                if args[0].input:
                    self.input = pyphon.Symbol(args[0].input)
                if args[0].output:
                    self.output = pyphon.Symbol(args[0].output)
                self.weight = args[0].weight
            else:
                # just an output symbol
                self.input = AnySymbol
                self.output = args[0]
        elif len(args) == 2:
            # input and output symbols
            self.input = args[0]
            self.output = args[1]
        elif len(args) == 3:
            # input, output, weight
            self.input = args[0]
            self.output = args[1]
            self.weight = args[2]

        for k,v in kwargs.iteritems():
            if k == 'input':
                self.input = v
            elif k == 'output':
                self.output = v
            elif k == 'weight':
                self.weight = v
            else:
                raise ValueError("Unknown keyword argument: %s" % k)
        return

    def __str__(self):
        eps = u'\u03b5'
        return "%s:%s %r" % (self.input or eps, self.output or eps,
                self.weight)

    def __repr__(self):
        return 'Label(%r, %r, %r)' % (self.input, self.output,
                self.weight)

    def __state(self):
        return (self.input, self.output, self.weight)

    def __cmp__(self, other):
        return cmp(self.__state(), other.__state())

    def __eq__(self, other):
        return self.__state() == other.__state()

    def __ne__(self, other):
        return self.__state() != other.__state()

    def __hash__(self):
        return hash(self.__state())

Epsilon = Label(None, None)
#=============================================================================

class Transducer(object):

    # Whether operations like concatenation, disjunction, kleene closure, etc.
    # should return minimized results.
    minimizeOperations = True

    def __init__(self, arcs=None):
        #self.sigma = sigma
        self.starts = []
        self.finals = []

        # node -> node -> [label,...]
        self.arcs = arcs or {}

        self.dotName = 'acceptor'
        self.dotRankdir = 'LR'
        self.dotShape = 'ellipse'
        self.dotStartStyle = 'filled'

    def __str__(self):
        return self.dot()

    def __len__(self):
        return len(self.nodes())

    def nodes(self):
        """
        Returns a list of the nodes in this Transducer. Each node is guaranteed
        to participate in at least one arc.
        """
        # FIXME: wow this is inefficient
        return list(set(self.starts + self.finals + self.arcs.keys()) | \
                set(reduce(operator.add, [v.keys() for v in \
                                          self.arcs.values()], [])))

    def symbols(self):
        """
        Returns the set of all symbols that appear on any arc in this
        Transducer.
        """
        symbols = set()
        for src, dest, label in self:
            symbols.add(label.input)
            symbols.add(label.output)
        return symbols

    def __contains__(self, nodeOrMappingOrLabel):
        #  it's a (toNode, fromNode, label)-triple
        if type(nodeOrMappingOrLabel) is tuple and len(nodeOrMappingOrLabel)==3:
            fromNode, toNode, label = nodeOrMappingOrLabel
            try:
                if label in self.arcs[fromNode][toNode]:
                    return True
                else:
                    return False
            except KeyError:
                return False

        # it's a (toNode, fromNode) pair
        elif type(nodeOrMappingOrLabel) is tuple and len(nodeOrMappingOrLabel)==2:
            fromNode, toNode = nodeOrMappingOrLabel
            try:
                if toNode in self.arcs[fromNode]:
                    return True
                else:
                    return False
            except KeyError:
                return False

        # it's a label
        elif isinstance(nodeOrMappingOrLabel, Label):
            for fromNode, to in self.arcs.iteritems():
                for toNode, labels in to.iteritems():
                    if nodeOrMappingOrLabel in labels:
                        return True
            return False

        # it's a node
        else:
            if not isinstance(nodeOrMappingOrLabel, Node):
                nodeOrMappingOrLabel = Node(nodeOrMappingOrLabel)
            try:
                return nodeOrMappingOrLabel in self.nodes()
                #return (nodeOrMappingOrLabel in self.arcs) or \
                #    any([nodeOrMappingOrLabel in v for v in self.arcs.values()])
            except KeyError:
                return False

        return None

    def __getitem__(self, fromNodeOrPair):
        if type(fromNodeOrPair) is tuple:
            fromNode, toNode = fromNodeOrPair
            return self.arcs[Node(fromNode)][Node(toNode)]

        return self.arcs[fromNodeOrPair]

    def __setitem__(self, fromNodeOrPair, dictOrLabel):
        if type(fromNodeOrPair) is tuple and len(fromNodeOrPair)==2:
            fromNode, toNode = fromNodeOrPair
            if not isinstance(fromNode, Node):
                fromNode = Node(fromNode)
            if not isinstance(toNode, Node):
                toNode = Node(toNode)
            if fromNode not in self.arcs:
                self.arcs[fromNode] = {}
            if toNode not in self.arcs[fromNode]:
                self.arcs[fromNode][toNode] = []

            if isinstance(dictOrLabel, Label):
                self.arcs[fromNode][toNode].append(dictOrLabel) # it's a label
            elif type(dictOrLabel) is tuple:
                self.arcs[fromNode][toNode].append(Label(*dictOrLabel)) 
            else:
                self.arcs[fromNode][toNode].append(Label(dictOrLabel))
            #else:
            #    raise TypeError('Arguments must be either (1) a node and a '
            #                    'dictionary, or (2) a pair of nodes and a '
            #                    'Label.')

        elif type(dictOrLabel) is dict:
            for labels in dictOrLabel.values():
                for label in labels:
                    if not isinstance(label, Label):
                        raise TypeError('Dictionary values must be '
                                'Labels')
            fromNode = isinstance(fromNodeOrPair, Node) and fromNodeOrPair or\
                Node(fromNodeOrPair)
            self.arcs[fromNode] = dictOrLabel # or copy?

        else:
            raise TypeError('Arguments must be either (1) a node and a '
                            'dictionary, or (2) a pair of nodes and a '
                            'Label.')

    def __delitem__(self, (fromNode, toNode, label)):
        self.arcs[Node(fromNode)][Node(toNode)].remove(label)

    def overwrite(self, otherTransducer):
        self.arcs, self.starts, self.finals = deepcopy((otherTransducer.arcs,
            otherTransducer.starts, otherTransducer.finals))

    def __iter__(self):
        for src, d in self.arcs.iteritems():
            for dest, labels in d.iteritems():
                for label in labels:
                    yield src, dest, label

    def setStarts(self, starts):
        nodes = self.nodes()
        # TODO: should these be the same objects as what's in self.arcs?
        starts = [isinstance(s, Node) and s or Node(s) for s in starts]
        for n in starts:
            if n not in nodes:
                self.arcs[n] = {}
                #raise ValueError('Desired start node %s not present in Transducer'\
                #        % n)
        self.starts = list(starts)

    def setFinals(self, finals):
        nodes = self.nodes()
        # TODO: should these be the same objects as what's in self.arcs?
        finals = [isinstance(f, Node) and f or Node(f) for f in finals]
        for n in finals:
            if n not in nodes:
                self.arcs[n] = {}
                #raise ValueError('Desired final node %s not present in '
                #        'Transducer' % n)
        self.finals = list(finals)

    dotHeader = \
    u"""
    digraph %(dotName)s {
    	rankdir=%(dotRankdir)s
    	size="8,5"
    	node [shape = %(dotShape)s];

        // arcs: source -> dest [label]
    %%s

        // start nodes
    %%s

        // final nodes
    %%s
    }
    """
    
    def dot(self, **kwargs):
        """
        Returns a string describing this Transducer in the graphviz dot
        formatting language, which may be used to generating pretty graphs.
        Optional keyword arguments may specify formatting options: dotName,
        dotRankdir, dotShape, dotStartStyle.
        """
        arcs = []
        for src, dest, label in self:
            arcs.append('\t"%s" -> "%s" [label="%s"];' % (src.dot(),
                dest.dot(), self.stringifyLabel(label)))
        finals = ['\t"%s" [peripheries=2];' % (f.dot(),) for f in self.finals]
        starts = ['\t"%s" [style=filled];' % (s.dot(),) for s in self.starts]

        headerDict = self.__dict__
        if kwargs:
            headerDict.update(kwargs)
        header = self.dotHeader % headerDict
        graph = header % ('\n'.join(arcs), '\n'.join(starts), '\n'.join(finals))
        return graph

    def stringifyLabel(self, label):
        return repr(label)

    def dotToFile(self, fileName, **kwargs):
        """
        Writes a Graphviz dot representation of this Transducer to the a
        file with the given path+name, possibly creating it. Arguments as for
        dot().
        """
        f = None
        try:
            f = codecs.open(fileName, 'w', 'utf-8')
            f.write(self.dot(**kwargs))
        finally:
            if f:
                f.close()

    def isDeterministic(self):
        # TODO
        pass

    def isComplete(self):
        # TODO
        pass

#    def accepts(self, form):
#        """
#        Returns C{True} iff the C{Transducer} accepts the given form.
#        TODO: epsilon transitions.
#        """
#        currentStates = set(self.starts)
#        for symbol in form:
#            nextStates = set()
#            for (origin, terminus, label) in self:
#                if origin in currentStates and label.input == symbol:
#                    # we found an arc for this symbol
#                    nextStates.add(terminus)
#            if not nextStates:
#                # we never found an arc for this symbol
#                return False
#            currentStates = nextStates
#            
#        # we made it all the way to the last symbol
#        # but are we in a final state?
#        if currentStates & set(self.finals):
#            return True
#        else:
#            return False

    def outputsFor(self, inputWord):
        # TODO: Make sure this will work with pyphon.Form as the inputWord.
        # TODO: Epsilons
        # The fsm might be nondeterministic or incomplete
        # we keep track of paths thru fsm here
        pathsSoFar = [[(start, '')] for start in self.starts] 
        for symbol in inputWord:
            newPaths = []
            for path in pathsSoFar:
                currentState = path[-1][0]
                for (origin, dest, label) in self:
                    if origin == currentState and symbol == label.input:
                        newPaths.append(path+[(dest, label.output)])
            pathsSoFar = newPaths

        # Build up the set/list of possible outputs corresponding to
        # each of the possible paths through the machine for the given inputWord
        outputs = []
        for path in pathsSoFar:
            #print path
            if path[-1][0] not in self.finals:
                continue
            output = ''.join([str(symbol) for (state, symbol) in path])
            outputs.append(output)
            
        return outputs

    def __epsilonInputClosure(origin, prefix=None):
        pass

    def inputsFor(self, outputWord):
        # Reverse Transduction
        # TODO: Make sure works with pyphon.Form
        # TODO: Epsilons
        # The fsm might be nondeterministic or incomplete
        # we keep track of paths thru fsm here
        pathsSoFar = [[(start, '')] for start in self.starts] 
        for symbol in outputWord:
            newPaths = []
            for path in pathsSoFar:
                currentState = path[-1][0]
                for (origin, dest, label) in self:
                    if origin == currentState and symbol == label.output:
                        newPaths.append(path+[(dest, label.input)])
            pathsSoFar = newPaths

        # Build up the set/list of possible inputs corresponding to
        # each of the possible paths through the machine for the given outputWord
        inputs = []
        for path in pathsSoFar:
            #print path
            if path[-1][0] not in self.finals:
                continue
            inputWord = ''.join([symbol for (state, symbol) in path])
            inputs.append(inputWord)
            
        return inputs

    def accepts(self, inputWord, outputWord):
        """
        Returns C{True} iff the C{Transducer} maps the given input form to the
        given output form.
        """
        return output in self.outputsFor(inputWord)

    def __add__(self, anotherFSA):
        """
        Returns an C{Transducer} that is the concatenation of this one
        with the given one. The result is nondeterministic.
        """
        #if len(self.finals) > 1 or len(anotherFSA.finals) > 1:
        #    print 'self.finals:', self.finals
        #    print 'another.finals:', anotherFSA.finals
        #    raise ValueError('Too many finals?')

        self = copy.deepcopy(self)
        anotherFSA = copy.deepcopy(anotherFSA)

        #selfData = self.finals[0].data
        #anotherData = anotherFSA.finals[0].data

        result = Transducer()
        for (fromNode, toNode, label) in self:
            result[fromNode, toNode] = Label(label)
        result.setStarts(list(self.starts))
        for (fromNode, toNode, label) in anotherFSA:
            result[fromNode, toNode] = Label(label)
        for f in self.finals:
            for anotherStart in anotherFSA.starts:
                result[f, anotherStart] = Label(Epsilon)
        result.setFinals(anotherFSA.finals)
        #for f in result.finals:
        #    f.data = '(%s%s)' % (selfData, anotherData)
        if Transducer.minimizeOperations:
            return result.minimized()
        else:
            return result

    def concatenation(self, anotherFSA):
        return self + anotherFSA

    def kleeneClosure(self, positive=False):
        """
        Returns the Kleene closure (star) of this acceptor. Id est, the
        acceptor that accepts the language of strings that consist of
        zero or more concatenations of strings from the original acceptor.
        If C{positive} is specified True, then the positive closure is
        returned, i.e., one (rather than zero) or more concatenations.
        The result is nondeterministic.
        """
        self = copy.deepcopy(self)

        result = Transducer()
        for (fromNode, toNode, label) in self:
            result[fromNode, toNode] = Label(label)

        newStart = nextNode()
        newFinal = nextNode()
        for s in self.starts:
            result[newStart, s] = Label(Epsilon)
        if not positive:
            result[newStart, newFinal] = Label(Epsilon)
        for f in self.finals:
            result[f, newFinal] = Label(Epsilon)
            result[f, newStart] = Label(Epsilon)
            #for s in self.starts:
            #    result[f, s] = Label(Epsilon)
        result.setStarts([newStart])
        result.setFinals([newFinal])
        if Transducer.minimizeOperations:
            return result.minimized()
        else:
            return result

    def disjunction(self, anotherFSA):
        """
        Returns the disjunction of this C{Transducer} with the given one, i.e.,
        a new C{Transducer} whose language is the union of the languages of this
        one and C{anotherFSA}. The result is nondeterministic.
        """
        self = copy.deepcopy(self)
        anotherFSA = copy.deepcopy(anotherFSA)

        result = Transducer()
        for (fromNode, toNode, label) in self:
            result[fromNode, toNode] = Label(label)
        for (fromNode, toNode, label) in anotherFSA:
            result[fromNode, toNode] = Label(label)

        newStart = nextNode()
        newFinal = nextNode()
        for s in self.starts:
            result[newStart, s] = Label(Epsilon)
        for s in anotherFSA.starts:
            result[newStart, s] = Label(Epsilon)
        result.setStarts([newStart])
        for f in self.finals + anotherFSA.finals:
            result[f, newFinal] = Label(Epsilon)
        result.setFinals([newFinal])
        if Transducer.minimizeOperations:
            return result.minimized()
        else:
            return result

    def __or__(self, anotherFSA):
        return self.disjunction(anotherFSA)

    def epsilonClosure(self, sources):
        """
        Returns the set of states in this Transducer that are reachable from any
        state in C{sources} on zero input (i.e., by some sequence of epsilon
        transitions). Logically, the result must be a superset of C{sources}.
        """
        result = set(sources)
        sources = list(sources)
        while sources:
            src = sources.pop(0)
            if src not in self.arcs:
                continue
            for dst, labels in self.arcs[src].iteritems():
                #print '%s -> %s (%r)' % (src, dst, labels)
                # XXX should we just be looking for epsilon inputs, not
                # Epsilon?
                if (Epsilon in labels) and (dst not in result):
                    result.add(dst)
                    sources.append(dst)
        return result

    def withoutEpsilons(self):
        """
        Returns a new C{Transducer} that accepts the same language as this one,
        but without any epsilon transitions. Based on Mohri's generic
        algorithm. This implementation will fail to remove any epsilon:epsilon
        transitions that have a non-None weight.
        """
        #print 'weps'
        self = copy.deepcopy(self)
        result = Transducer()
        for p in self.nodes():
            #print 'p = %r' % p
            if p in self.arcs:
                for pDest, labels in self.arcs[p].iteritems():
                    for label in labels:
                        #print 'considering %r -> %r [%r]' % (p,pDest,label)
                        if label != Epsilon and (p,pDest,label) not in result:
                            #print 'keeping non-epsilon trans: %r -> %r [%r]' % \
                            #    (p,pDest,label)
                            result[p, pDest] = Label(label)
            for q in self.epsilonClosure([p]):
                #print 'q = %r' % q
                if q in self.arcs:
                    for qDest, labels in self.arcs[q].iteritems():
                        for label in labels:
                            if label != Epsilon and (p,qDest,label) not in result:
                                #print 'non-eps qDest: %r -> %r [%r]' % (p,qDest,label)
                                result[p, qDest] = Label(label)
                if q in self.finals and p not in result.finals:
                    result.finals.append(p)
        #result.start = self.start
        result.setStarts(list(self.starts))
        return result.trim()

    def trim(self):
        """
        Removes unreachable and unfinishable states in-place. Returns self.
        """
        #print self.dot()
        # reachability
        nodes = self.nodes()#set(self.nodes() + self.finals)
        reachable = dict([(n,False) for n in nodes])
        revreachable = dict([(n,False) for n in nodes])
        #print "Trimming [%d nodes]..." % len(nodes)

        def touch(p):
            if reachable[p]:
                return
            reachable[p] = True
            if p in self.arcs:
                for q in self.arcs[p]:
                    touch(q)

        def reverseTouch(p):
            if revreachable[p]:
                return
            revreachable[p] = True
            for src, dest, lab in self:
                if (dest == p):
                    reverseTouch(src)

        #print 'Touching starts...'
        for s in self.starts:
            touch(s)
        #print '...done touching starts'

        for f in self.finals:
            reverseTouch(f)

        toDel = [(src, dest, lab) for (src, dest, lab) in self if \
                (not reachable[src]) or \
                (not revreachable[dest])]
        for arc in toDel:
            del self[arc]

        for p in list(self.finals):
            if not reachable[p]:
                self.finals.remove(p)
        for p in list(self.starts):
            if not revreachable[p]:
                self.starts.remove(p)

        return self

    def reversed(self):
        """
        Returns the reversal of this Transducer: a new Transducer with all arcs
        reversed and start/final states swapped.
        """
        #print 'rev'
        self = copy.deepcopy(self)
        result = Transducer()
        newStates = {}
        for src,dest,label in self:
            #if src not in newStates:
            #    newStates[src] = nextNode()
            #if dest not in newStates:
            #    newStates[dest] = nextNode()
            result[newStates.setdefault(dest, nextNode()), 
                   newStates.setdefault(src, nextNode())] = Label(label)

        result.setStarts([newStates.setdefault(f, nextNode()) for f in \
                self.finals])
        result.setFinals([newStates.setdefault(s, nextNode()) for s in \
                self.starts])
        return result

    def labelsFrom(self, states):
        """
        Returns the set of labels that appear on any outgoing arc from any of
        the given states.
        """
        labels = set()
        for s in states:
            if s in self.arcs:
                for dest,slabels in self.arcs[s].iteritems():
                    for slabel in slabels:
                        labels.add(slabel)
        return labels

    def destsFrom(self, srcStates, label, ignoreWeights=True):
        """
        Returns the set of states that can be reached from any state in srcStates
        via an arc with the given label.
        """
        dests = set()
        for src in srcStates:
            if src in self.arcs:
                for dest, dLabels in self.arcs[src].iteritems():
                    if ignoreWeights:
                        for dl in dLabels:
                            if label.input == dl.input and \
                                    label.output == dl.output:
                                dests.add(dest)
                    elif label in dLabels:
                        dests.add(dest)
        return dests

    def determinized(self, renameStates=True, weightFn=None):
        """
        Returns the deterministic Transducer that results from taking the subset
        construction of this possibly nondeterminisitc, but epsilon-free
        Transducer. The weightFn argument is important and should be documented.
        When it's None, we treat the machine as an unweighted acceptor of
        (i,o,w) triples.
        """
        #print 'det'
        dfa = Transducer()
        newStates = []
        stateNames = {}
        #if not weightFn:
        #    weightFn = lambda ns, destStateSet, label, mac: None
        
        stateNames[frozenset(self.starts)] = nextNode()
        if renameStates:
            dfa.starts = [stateNames[frozenset(self.starts)]]
        else:
            dfa.starts = [frozenset(self.starts)]
        newStates.append(frozenset(self.starts))

        while newStates:
            ns = newStates.pop()
            if ns not in dfa.finals:
                for s in ns:
                    if s in self.finals:
                        if renameStates:
                            dfa.finals.append(stateNames[ns])
                        else:
                            dfa.finals.append(ns)
                        break
            for label in self.labelsFrom(ns):
                if label.input is label.output is None:
                    raise ValueError('Cannot determinize an Transducer with '
                                     'Epsilon transitions. Use '
                                     'Transducer.withoutEpsilons() first.')
                destStateSet = frozenset(self.destsFrom(ns, label,
                        ignoreWeights=bool(weightFn)))
                if weightFn:
                    weight = weightFn(ns, destStateSet, label, self)
                else:
                    weight = label.weight
                label = Label(label, weight=weight)
                if destStateSet not in stateNames:
                    stateNames[destStateSet] = nextNode()

                if renameStates:
                    if stateNames[destStateSet] not in dfa.nodes():
                        newStates.append(destStateSet)
                else:
                    if destStateSet not in dfa.nodes():
                        newStates.append(destStateSet)

                if (ns, destStateSet, label) in dfa or \
                        (stateNames[ns], stateNames[destStateSet], label) in dfa:
                    continue

                if renameStates:
                    dfa[stateNames[ns], stateNames[destStateSet]] = label
                else:
                    dfa[ns, destStateSet] = label
        return dfa.trim()

    def minimized(self):
        #print 'min'
        return self.withoutEpsilons()\
                .reversed().determinized()\
                .reversed().determinized()

    def prefixTransducer(self, state):
        """
        Returns an Transducer of the prefix or left language of the given
        state in this machine.
        """
        return self.reversePrefixTransducer(state).reversed().trim()

    def reversePrefixTransducer(self, state):
        """
        Returns an Transducer of the reverse-prefix or reverse-left language
        of the given state in this machine.
        """
        result = copy.deepcopy(self)
        result.setFinals([state])
        return result.reversed().trim()

    def subPrefixTransducer(self, state):
        """
        Returns an Transducer of any substring of any word in the prefix or left
        language of the given state.
        """
        pa = self.prefixTransducer(state)
        pa.setFinals(pa.nodes())
        return pa

    def reverseSubPrefixTransducer(self, state):
        """
        Returns an Transducer of any substring of any word in the reverse-prefix
        or reverse-left language of the given state.
        """
        pa = self.reversePrefixTransducer(state)
        pa.setFinals(pa.nodes())
        return pa

    def intersection(self, anotherFSA):
        """
        Returns an Transducer of the intersection of the languages of self and
        anotherFSA. Faster if self is sparser than anotherFSA.
        """
        print 'FST intersection'
        result = Transducer()
        nextStates = [(s1, s2) for s1 in self.starts for s2 in anotherFSA.starts]
        stateNames = dict([(ns, nextNode()) for ns in nextStates])

        while nextStates:
            #print 'nextStates = %s' % nextStates
            s1, s2 = nextStates.pop(0)
            if s1 in self.finals and s2 in anotherFSA.finals:
                #return True
                result.finals.append(stateNames[(s1,s2)])
            if s1 in self.starts and s2 in anotherFSA.starts:
                result.starts.append(stateNames[(s1,s2)])

            selfLabels = self.labelsFrom([s1])
            otherLabels = anotherFSA.labelsFrom([s2])
            for label in (selfLabels & otherLabels):
                selfDests = self.destsFrom([s1], label)
                otherDests = anotherFSA.destsFrom([s2], label)
                for (d1, d2) in [(d1,d2) for d1 in selfDests for d2 in \
                        otherDests]:

                    if (d1,d2) not in stateNames:
                        stateNames[(d1,d2)] = nextNode()
                        nextStates.append((d1,d2))

                    src = stateNames[(s1,s2)]
                    dst = stateNames[(d1,d2)]
                    result[src, dst] = Label(label)

        return result.trim()

        if Transducer.minimizeOperations:
            return result.minimized()
        else:
            return result

    def __and__(self, anotherFSA):
        """
        Returns a Transducer of the intersection of the languages of self and
        anotherFSA. Faster if self is sparser than anotherFSA.
        """
        return self.intersection(anotherFSA)

    def isomorphism(self):
        result = Transducer()
        rnames = {}
        for src, dest, label in self:
            rsrc = rnames.setdefault(src, nextNode())
            rdest = rnames.setdefault(dest, nextNode())
            result[rsrc, rdest] = Label(label)

            if src in self.finals and rsrc not in result.finals:
                result.finals.append(rsrc)
            if src in self.starts and rsrc not in result.starts:
                result.starts.append(rsrc)
            if dest in self.finals and rdest not in result.finals:
                result.finals.append(rdest)
            if dest in self.starts and rdest not in result.starts:
                result.starts.append(rdest)
        return result, rnames

    def maxCommonSuffix(self, state):
        """
        Returns the state with which the given state shares the longest common
        suffix. I.e., the highest rank state whose reverse prefix acceptor's
        intersection with the reverse subprefix acceptor of the given state is
        non-empty (has a final state).
        """
        stateRevSubP = self.reverseSubPrefixTransducer(state)
        mergeables = {}
        # identify mergeable nodes
        for other in self.nodes():
            if other == state:
                continue
            otherRevP = self.reversePrefixTransducer(other)
            ixn = otherRevP & stateRevSubP
            if ixn.finals:
                mergeables[other] = ixn
        if not mergeables:
            return None

        maxSize = max([len(ixn) for m,ixn in mergeables.iteritems()])
        mergeablesLeft = [m for m,ixn in mergeables.iteritems() if len(ixn) == maxSize]

        if len(mergeablesLeft) != 1:
            print "HOLOCAUST PRIME: can't decide which of %r to merge %s "\
                  "with!" % (mergeablesLeft, state)
            print "The fires of intersection:"
            for m in mergeablesLeft:
                print '%s & %s:' % (state, m)
                print mergeables[m].dot()
                print
            print 'size of intersection of intersections:',
            print len(mergeables[mergeablesLeft[0]] & \
                    mergeables[mergeablesLeft[1]])
            raise ValueError()
        return mergeablesLeft[0]

    def expandAnySymbol(self, inventory, exceptInOut=None, identityOnly=False):
        """
        Expands @-symbols in place.
        """
        #print 'expand @, inv =', inventory
        toExpand = []
        for fromNode, toNode, label in self:
            if AnySymbol in (label.input, label.output):
                toExpand.append((fromNode, toNode, label))
        for fromNode, toNode, label in toExpand:
            del self[fromNode, toNode, label]
            inputs = label.input == AnySymbol and inventory or [label.input]
            outputs = label.output == AnySymbol and inventory or [label.output]
            for i in inputs:
                for o in outputs:
                    if exceptInOut and (i,o)==exceptInOut:
                        continue
                    if identityOnly and (i != o):
                        print 'hi'
                        continue
                    self[fromNode, toNode] = Label(i, o)
        #self.dotToFile('expanderoo.dot')

    def addDeletionSelfLoops(self, inventory, deletionSymbol=None, weight=None):
        for node in self.nodes():
            for symbol in inventory:
                alreadyDeleted = False
                if node in self.arcs:
                    for dest, labels in self[node].iteritems():
                        for label in labels:
                            if label.input == symbol and label.output in\
                            (deletionSymbol, None):
                                alreadyDeleted = True
                                break
                        if alreadyDeleted:
                            break
                if alreadyDeleted:
                    continue
                #print 'adding del self loop to node %s: %s -> %s' % (node,
                #        symbol, deletionSymbol)
                self[node, node] = Label(symbol, deletionSymbol, weight)

        #self.dotToFile('deleteroo.dot')
        #raw_input('SS')


    def removeNode(self, node):
        """
        It's easy when you're Jesus, LOL.
        """
        if node in self.arcs:
            del self.arcs[node]
        for src, destDic in self.arcs.iteritems():
            if node in destDic:
                del destDic[node]
        if node in self.starts:
            self.starts.remove(node)
        if node in self.finals:
            self.finals.remove(node)

    def splitStateOnIncoming(self, state, keepFinal=True):
        """
        In place. Returns the splittoids.
        """
        newArcs = []
        splits = []
        startSplit = state in self.starts and nextNode() or None
        for src, dest, label in self:
            #if startSplit and src == state:
            #    if dest == state:
            #        newArcs.append((startSplit, startSplit, label))
            #    else:
            #        newArcs.append((startSplit, dest, label))
            if dest == state:
                # an incoming arc to the state
                split = nextNode()
                splits.append(split)
                newArcs.append((src, split, label))
                if state in self.arcs:
                    for splitDest, labels in self.arcs[state].iteritems():
                        for l in labels:
                            if splitDest == state:
                                newArcs.append((split, split, l))
                            else:
                                newArcs.append((split, splitDest, l))

        for src, dest, label in newArcs:
            self[src, dest] = label
        #if startSplit:
        #    self.starts.append(startSplit)

        if keepFinal:
            if state in self.starts:
                startSplit = nextNode()
                
            for s in splits:
                if state in self.finals:
                    self.finals.append(s)

        self.removeNode(state)
        #print 'Split %r into %r' % (state, splits)
        return splits

    def successors(self, nodes):
        """
        Returns list of nodes that are in the successor sets of any of the given
        nodes.
        """
        #sys.stdout.write('successors of %d nodes...' % len(nodes))
        #sys.stdout.flush()

        allNodes = self.nodes()
        tDic = dict([((a,b),0) for a in allNodes for b in allNodes])
        for (a,b) in tDic.keys():
            if a==b or (a,b) in self: tDic[(a,b)]=1
        for x in allNodes:
            for (a,b) in tDic.keys():
                tDic[(a,b)] = tDic[(a,b)] or (tDic[(a,x)] and tDic[(x,b)])

        succs = dict([(node,[q for ((p,q),v) in tDic.items() if node==p and v])
            for node in allNodes])

        result = set()
        for node in nodes:
            for succ in succs[node]:
                result.add(succ)
        #sys.stdout.write(' done.\n')
        #sys.stdout.flush()
        return result
                
#=============================================================================

#class Transducer(Acceptor):
#
#    def __setitem__(self, fromNodeOrPair, dictOrLabel):
#        if type(fromNodeOrPair) is tuple:
#            fromNode, toNode = fromNodeOrPair
#            if fromNode not in self.arcs:
#                self.arcs[fromNode] = {}
#            if toNode not in self.arcs[fromNode]:
#                self.arcs[fromNode][toNode] = set()
#
#            if type(dictOrLabel) is tuple:
#                self.arcs[fromNode][toNode].append(TransducerLabel(*dictOrLabel))
#            elif isinstance(dictOrLabel, TransducerLabel):
#                self.arcs[fromNode][toNode].append(dictOrLabel) # it's a label
#            else:
#                raise TypeError('Arguments must be either (1) a node and a '
#                                'dictionary, or (2) a pair of nodes and a '
#                                'TransducerLabel.')
#
#        elif type(dictOrLabel) is dict:
#            for labels in dictOrLabel.values():
#                for label in labels:
#                    if not isinstance(label, TransducerLabel):
#                        raise TypeError('Dictionary values must be '
#                                'TransducerLabels')
#            self.arcs[fromNode] = dictOrLabel # or copy?
#
#        else:
#            raise TypeError('Arguments must be either (1) a node and a '
#                            'dictionary, or (2) a pair of nodes and a '
#                            'TransducerLabel.')
#
#
#
#    def languageOnLexicon(self, inputs):
#        pass

#=============================================================================

def makeSymbolTransducer(inSymbol, outSymbol):
    """
    Creates and returns a Transducer of a single given pair of input-output
    Symbols.
    """
    n0, n1 = nextNode(), nextNode()
    acceptor = Transducer()
    acceptor[n0, n1] = inSymbol, outSymbol
    acceptor.setStarts([n0])
    acceptor.setFinals([n1])
    return acceptor

